`
https://leetcode.cn/problems/successful-pairs-of-spells-and-potions/
`

/**
 * 该解法适合 spells 和 potions 数组里的数字范围比较大
 */

/**
 * @param {number[]} spells
 * @param {number[]} potions
 * @param {number} success
 * @return {number[]}
 */
var successfulPairs = function (spells, potions, success) {
  const sps = spells
    // 记录原本顺序
    .map((s, i) => [s, i])
    // 预排序，方便双指针
    .sort((a, b) => a[0] - b[0])
  const needs = potions
    // 预排序，方便双指针
    .sort((a, b) => a - b)
    // 计算出每一个 potions 至少需要多少能量强度才能成功组合
    .map((p) => success / p)
  const res = new Array(sps.length).fill(0)
  let j = needs.length - 1
  // 双指针能够让每个 needs 只遍历一次
  // 后面的 spell 能够复用前面的结果
  for (let i = 0; i < sps.length; i++) {
    while (j >= 0 && sps[i][0] >= needs[j]) {
      j--
    }
    res[i] = needs.length - 1 - j
  }
  // 恢复原本顺序
  const resRaw = new Array(res.length).fill(0)
  for (let i = 0; i < res.length; i++) {
    resRaw[sps[i][1]] = res[i]
  }
  return resRaw
};